package 算法图解;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/20 10:16
 * 每次在广播中选择能够覆盖未覆盖的最大广播
 * 表示广播覆盖的集合 , 使用 map , key 为广播名 , value 为 set 集合 , 表示能够覆盖的地方
 * 最终结果集合，选取了哪些广播
 * 未覆盖的集合
 * 已经覆盖的集合
 */
public class 集合覆盖 {
    public static void main(String[] args) {
        Map<String, Set<String>> broadcasts = new HashMap<>();
        Set<String> states_needed = new LinkedHashSet<>();
        System.out.println(createFinal(broadcasts, states_needed));

    }

    public static void createData(Map<String, Set<String>> broadcasts, Set<String> states_needed) {
        List<String> names = Arrays.asList("one", "two", "three", "four", "five");
        List<Set<String>> lists = new LinkedList<>();
        lists.add(new LinkedHashSet<>(Arrays.asList("id", "nv", "ut")));
        lists.add(new LinkedHashSet<>(Arrays.asList("wa", "id", "mt")));
        lists.add(new LinkedHashSet<>(Arrays.asList("or", "nv", "ca")));
        lists.add(new LinkedHashSet<>(Arrays.asList("nv", "ut")));
        lists.add(new LinkedHashSet<>(Arrays.asList("ca", "az")));
        for (int i = 0; i < names.size(); i++)
            broadcasts.put(names.get(i), lists.get(i));
        states_needed.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az"));
    }

    public static Set<String> createFinal(Map<String, Set<String>> broadcasts, Set<String> states_needed) {
        createData(broadcasts, states_needed);
        Set<String> final_broadcast = new LinkedHashSet<>();
        while (!states_needed.isEmpty()) {
            Set<String> states_covered = new LinkedHashSet<>();
            String best_broadcast = "";
            Set<Map.Entry<String, Set<String>>> entries = broadcasts.entrySet();
            for (Map.Entry<String, Set<String>> entry : entries) {
                Set<String> tmp = entry.getValue();
                tmp.retainAll(states_needed);
                if (tmp.size() > states_covered.size()) {
                    states_covered = tmp;
                    best_broadcast = entry.getKey();
                }
            }
            broadcasts.remove(best_broadcast);
            states_needed.removeAll(states_covered);
            final_broadcast.add(best_broadcast);
        }
        return final_broadcast;
    }

}




